package com.sali.Tree;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
 */
public class LeetCode_99 {

    public void recoverTree(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();

        TreeNode errorOne = null;
        TreeNode errorTwo = null;
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            TreeNode cur = stack.pop();

            if (pre != null && pre.val >= cur.val) {
                if (errorOne == null) {
                    errorOne = pre;
                    errorTwo = cur;
                } else {
                    errorTwo = cur;
                }
            }
            pre = cur;

            root = cur.right;
        }

        Integer tmp = errorOne.val;
        errorOne.val = errorTwo.val;
        errorTwo.val = tmp;
    }

}
